package tree.heap.arrayUse0IndexHeap;

import java.util.*;

/**
 * 功能描述: 大顶堆/小顶堆 工具类
 * 2024/05/27
 * <p>
 * ZhangYi
 */
public class HeapArrayUtils {

    /**
     * 功能描述: 小顶堆
     * 2024/05/27
     * <p>
     * ZhangYi
     */
    public static class MinTopHeapUtils<T>{
        private int heapSize;
        private List<T> dataList;
        private Comparator<T> comparator;

        public MinTopHeapUtils( Comparator<T> comparator) {
            this.dataList = new ArrayList<>();
            this.comparator = comparator;
            this.heapSize =0;
        }


        /**
         * 功能描述: 插入元素
         * 2024/05/27
         * <p>
         * ZhangYi
         */
        public void push(T val){
            if (val == null){
                throw new RuntimeException("val is null");
            }
            this.dataList.add(val);
            heapInsert(val,heapSize++);
        }

        public T pop(){
            if (heapSize == 0){
                throw new RuntimeException("heap is empty");
            }
            T val = this.dataList.get(0);
            swapValue(0,--heapSize);
            heapfiy(0,heapSize);
            return val;
        }

        private void heapfiy(int index,
                             int heapSize) {
            int leftIndex = (index<<1) | 1;
            while (leftIndex<heapSize){
                int smallestIndex = leftIndex +1 <heapSize && comparator.compare(this.dataList.get(leftIndex+1) ,this.dataList.get(leftIndex))<0? leftIndex +1 : leftIndex;

                smallestIndex = comparator.compare(this.dataList.get(smallestIndex),this.dataList.get(index))<0 ? smallestIndex : index;

                if (smallestIndex ==index){
                    break;
                }
                swapValue(index,smallestIndex);
                index = smallestIndex;
                leftIndex = (index<<1) | 1;
            }
        }

        /**
         * 功能描述: 插入元素,调整堆中的位置, 越小的越靠近 索引 0 位置
         * 2024/05/27
         * <p>
         * ZhangYi
         */
        private void heapInsert(T val,
                                int index) {
            while (this.comparator.compare(this.dataList.get(index),this.dataList.get((index-1)/2))<0){
                swapValue(index,(index-1)/2);
                index = (index-1)/2;
            }
        }

        private void swapValue(int index,
                               int index2) {
            T temp = this.dataList.get(index);
            this.dataList.set(index,this.dataList.get(index2));
            this.dataList.set(index2,temp);
        }
    }


    public static class MaxTopheapUtils<T>{
        private int heapSize;

        private int limitSize = 1000;
        private List<T> dataList;
        private Comparator<T> comparator;

        public MaxTopheapUtils( Comparator<T> comparator) {
            this.dataList = new ArrayList<>();
            this.comparator = comparator;
            this.heapSize =0;
        }

        public MaxTopheapUtils( Comparator<T> comparator,int limitSize) {
            this.dataList = new ArrayList<>();
            this.comparator = comparator;
            this.heapSize =0;
            this.limitSize = limitSize;
        }

        public boolean isEmpty(){
            return this.dataList.size() ==0;
        }

        public boolean isFull(){
            return this.dataList.size() == this.limitSize;
        }

        public void push(T val){
            if (val == null){
                throw new RuntimeException("val is null");
            }
            if (limitSize > 0 && this.dataList.size() == this.limitSize){
                throw new RuntimeException("heap is full,push Refuse");
            }
            this.dataList.add(val); // 这里只能用 add 添加, set ,get  如果是一个空的 list, 操作索引会报错
            heapInsert(val,heapSize++);
        }


        public T pop(){
            if (isEmpty()){
                throw new RuntimeException("heap is empty");
            }
            T val = this.dataList.get(0);
            swapValue(0,--heapSize);
            heapfiy(0,heapSize);
            return val;
        }

        private void heapfiy(int index,
                             int heapSize) {

            int leftInex = (index<<1) | 1;
            while (leftInex<heapSize){
                int largestIndex = leftInex +1 < heapSize && comparator.compare(this.dataList.get(leftInex+1),this.dataList.get(leftInex))< 0 ? leftInex +1 : leftInex;

                largestIndex = comparator.compare(this.dataList.get(largestIndex),this.dataList.get(index))< 0 ? largestIndex : index;
                if (largestIndex == index){
                    break;
                }
                swapValue(index,largestIndex);
                index = largestIndex;
                leftInex = (index << 1) |1;
            }
        }

        private void heapInsert(T val,
                                int index) {
            while (this.comparator.compare(this.dataList.get(index),this.dataList.get((index-1)/2)) <0){
                swapValue(index,(index-1)/2);
                index = (index-1)/2;
            }
        }

        private void swapValue(int index,
                               int index2) {
            T temp = this.dataList.get(index);
            this.dataList.set(index,this.dataList.get(index2));
            this.dataList.set(index2,temp);
        }

    }

    public static void main(String[] args) {
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,
                               Integer o2) {
                return o1 - o2;
            }
        };
        System.out.println("小顶堆测试 ==");
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(comparator);
        MinTopHeapUtils<Integer> heap = new MinTopHeapUtils<>(comparator);

        List<Integer> list = Arrays.asList(11, 2, 3, 41, 5, 16, 7, 8, 19, 10);

        for (Integer integer : list) {
            priorityQueue.add(integer);
            heap.push(integer);
        }

        while (priorityQueue.size()>0){
            System.out.println(priorityQueue.poll());
            System.out.println(heap.pop());
        }

        // 大顶堆测试
        Comparator<Integer> integerComparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1,
                               Integer o2) {
                return o2-o1;
            }
        };

        System.out.println("大顶堆测试 ==");
        PriorityQueue<Integer> priorityQueue1 = new PriorityQueue<>(integerComparator);
        MaxTopheapUtils<Integer> heap1 = new MaxTopheapUtils<>(integerComparator);

        for (Integer integer : list) {
            priorityQueue1.add(integer);
            heap1.push(integer);
        }

        while (!priorityQueue1.isEmpty()){
            System.out.println(priorityQueue1.poll());
            System.out.println(heap1.pop());
        }


    }
}
